\subsection{Brute Force Algorithm}
\label{subsec:brute-force}

The brute force algorithm is a naive algorithm that simply tries every possible
assignment, evaluates it with the given cost function and eventually returns the
optimal assignment.

\subsubsection{Pseudo Code}

\begin{figure} [t]
  
  \centering
  \begin{algorithmic} 
    \STATE \textbf{PROCEDURE} BF(Demand $D$) \textbf{returns} Assignment:
    
    \STATE let $A \leftarrow $ empty Assignment
    \RETURN BF-Rec($D$, $A$)
    
    \STATE $~$
    
    \STATE \textbf{PROCEDURE} BF-Rec(Demand $D$, Assignment $A$) \textbf{returns} Assignment:

    \IF{$|D|=0$}
    \RETURN $A$

    \ELSE
    \STATE let $L \leftarrow \emptyset$
    \STATE let $s \leftarrow $ first shift $\in D$ which $\notin A$
    \STATE let $D' \leftarrow D \setminus \{s\}$

    \FORALL{$d \in Departments_{A}$}
    \STATE $A' \leftarrow A \cup \{s$ has been assigned to $d\}$
    \STATE $L \leftarrow L \cup \{$ BF-Rec($D'$, $A'$) $\}$
    \ENDFOR
    
    \STATE let $A_{Best} \leftarrow$ NULL
    \FORALL{$A' \in L$}
    \IF{Cost($A'$) $<$ Cost($A_{Best}$) $\wedge$ $A_{Best} =$ NULL}
    \STATE let $A_{Best} \leftarrow A'$
    \ENDIF
    \ENDFOR

    \RETURN $A_{Best}$

    \ENDIF
    
  \end{algorithmic}

  \caption{Pseudo-code of a brute force algorithm that finds an optimal assignment.}
  \label{fig:brute-force}
\end{figure}

The task of the algorithm is quite simple: in each step, try out a new combination of
shift assignments and return the best result for each possible choice, as long
as there are new combinations possible.

We model this behavior in a recursive algorithm as depicted in
Fig. \ref{fig:brute-force}. The algorithm recursively assigns shifts to
departments in an initially empty assignment, branching out in each recursion
step and selecting in each branch a different department. This is repeated until
there are no more shifts to assign. If this is the case, the current assignment
is simply returned and the recursion terminates.

From the set of assignments created for each shift in the demand, the assignment
with the smallest cost is selected and returned to the caller. By recursively
unwinding, the best assignment in the entire search tree is found, which is the
optimal solution to the given demand.


\subsubsection{Conclusion}

While the brute force algorithm yields always the optimal result, it is obvious
that this algorithm is impractical for finding a solution to the
problem. Branching out recursively for each possible assignment of a shift makes
the memory consumption and running time explode. The running time will be
analyzed in Sec. \ref{subsec:brute-force-cost}.
